package org.example.Backtracking_algorithm;

import java.lang.reflect.MalformedParameterizedTypeException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Alphabet_combinations_of_phone_numbers {
    public static LinkedList<Character> path = new LinkedList<>();
    public static LinkedList<String> arr = new LinkedList<>();
    public static HashMap<Character, String> map = new HashMap<Character, String>(){{
        put('2',"abc");
        put('3',"def");
        put('4',"ghi");
        put('5',"jkl");
        put('6',"mno");
        put('7',"pqrs");
        put('8',"tuv");
        put('9',"wxyz");
    }};
    public static void main(String[] args) {
        //电话号码的字母组合

        //给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
        //给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
        letterCombinations("");
        for (int i = 0; i < arr.size(); i++) {
            System.out.print(arr.get(i)+" ");
        }
    }
    public static List<String> letterCombinations(String digits) {
        if (digits.length()==0) return arr;
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) {
            char a = digits.charAt(i);
            list.add(map.get(a));
        }
        get(list,0);
        return arr;
    }
    public static void get(ArrayList<String> list,int index){
        if (path.size()==list.size()){
            StringBuffer sb = new StringBuffer(path.size());
            for (Character c : path) {
                sb.append(c);
            }
            arr.add(sb.toString());
            return;
        }
        for (int i = 0; i < list.get(index).length(); i++) {
            path.add(list.get(index).charAt(i));
            get(list,index+1);
            path.removeLast();
        }
    }
}
